package leetcode.editor.cn;

public class P375GuessNumberHigherOrLowerIi {
    public static void main(String[] args) {
        Solution solution = new P375GuessNumberHigherOrLowerIi().new Solution();
        System.out.println(solution.getMoneyAmount(10));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
         int N = 210;
         int[][] cache = new int[N][N];
        public int getMoneyAmount(int n) {

            return getMoney(1, n);
        }

        private int getMoney(int low, int high) {
            if (low >= high) return 0;
            if (cache[low][high] != 0) return cache[low][high];
            int max = 0x3f3f3f3f;
            for (int i = low; i <= high; i++) {
                int cur = Math.max(getMoney(low, i - 1), getMoney(i + 1, high)) + i;
                max = Math.min(max, cur);
            }
            cache[low][high] = max;
            return max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}